#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <malloc.h>

using namespace std;

const int SailPlace = 4, CreatePlace = 3; // N代表销地， M代表产地

int B03[SailPlace] = {3, 6, 5, 6}; // N个销地
int A03[CreatePlace] = {7, 4, 9};  // M个产地
int judgeA03[CreatePlace] = {7, 4, 9};

int back03[CreatePlace + 1][SailPlace + 1]; // 存储备用方案
// int ans03[CreatePlace][SailPlace];//存储最优方案

int ui_vj[CreatePlace + 1][SailPlace + 1]; // 存储位势表（ui+vj）表， 多出来的一行存储位势
int space_check[CreatePlace][SailPlace];

// 逆时针坐标变化
//              上  左  下  右
//              0   1   2   3
int x03[5] = {0, -1, 0, 1};
int y03[5] = {1, 0, -1, 0};

// M行N列运价表
int priceij[CreatePlace][SailPlace] =
    {
        {3, 11, 3, 10},
        {1, 9, 2, 8},
        {7, 4, 10, 5}};

// i->j每个单位的运价
struct price
{
    int i;   // ai地为销地
    int j;   // bj地为产地
    int cij; // ai地运向bj地 的单位价格

    bool operator<(const price &other) const // 自定义排序
    {
        return cij < other.cij;
    }
};

// 记录回路上的顶点
struct Point
{
    int ii, jj; // 坐标
    int num;    // 运输量
    int xuhao;  // 回路上的序号
};

// 每一次回路的数据
struct loop
{
    int start_deri;     // 出发的方向 （1\2\3\4）
    int i, j;           // 出发点空格的坐标
    vector<Point> path; // 记录回路经过的顶点
    // 物理下标是从0开始的
    // 逻辑下标是从1开始的
};

vector<loop> vlopp;

// 自定义比较类
struct ComparePrice
{
    bool operator()(const price &a, const price &b) const
    {
        return a.cij > b.cij;
    }
};

// priority_queue<price, vector<price>, greater<price>> qu03; //最小堆
priority_queue<price, vector<price>, ComparePrice> qu03; // 最小堆

bool stB[SailPlace];   // 标记每一列是否被划掉，如果stB[i] == false(表示被划掉), 说明B[i] == 0, 表示bi销地已经不需要进货了
bool stA[CreatePlace]; // 标记每一行是否被划掉，如果stA[i] == false(表示被划掉), 说明A[i] == 0, 表示ai产地已经不能再出货了

void print()
{
    cout << "最优可行方案如下：" << endl;

    cout << "     B1   B2   B3   B4   " << endl;

    for (int i = 0; i < CreatePlace; i++)
    {
        cout << "A" << i + 1 << "   ";
        for (int j = 0; j < SailPlace; j++)
        {
            printf("%-5d", back03[i][j]);
        }
        cout << endl;
    }

    cout << endl;
    cout << "总费用为：";
    int sum = 0, sumIscal = 0;
    int sumCreate = 0;
    for (int i = 0; i < CreatePlace; i++)
        sumCreate += judgeA03[i];
    for (int i = 0; i < CreatePlace; i++)
    {
        for (int j = 0; j < SailPlace; j++)
        {
            if (back03[i][j])
            {
                cout << back03[i][j] << " * " << priceij[i][j];
                sum += back03[i][j] * priceij[i][j];
                sumIscal += back03[i][j];
                if (sumIscal < sumCreate)
                    cout << " + ";
                else
                {
                    cout << " = " << sum << endl;
                    break;
                }
            }
        }
    }
}

// 最小元素法
void findmin()
{
    memset(stB, true, sizeof stB);
    memset(stA, true, sizeof stA);     // 初始时刻，都没有被划掉
    int cnt = SailPlace + CreatePlace; // 计数器

    while (cnt && !qu03.empty()) // cnt == 0时退出
    {
        price p = qu03.top(); // 取出最小的
        qu03.pop();

        if (stB[p.j] == true && stA[p.i] == true)
        {
            if (A03[p.i] > B03[p.j])
            {
                back03[p.i][p.j] = B03[p.j];

                A03[p.i] -= B03[p.j];
                B03[p.j] = 0; // Bj不再有需求，而产地Ai还有剩余的货物
                stB[p.j] = false;
                cnt--;
            }
            else if (A03[p.i] == B03[p.j])
            {
                back03[p.i][p.j] = B03[p.j];

                A03[p.i] = 0;
                B03[p.j] = 0;
                stA[p.i] = false;
                stB[p.j] = false;
                cnt--;
            }
            else
            {
                back03[p.i][p.j] = A03[p.i];

                B03[p.j] -= A03[p.i];
                A03[p.i] = 0; // Ai现有的货物全部运往Bj, Bj任然有需求
                stA[p.i] = false;
                cnt--;
            }
        }
    }
}

// 利用位势法求解最优方案
void Weishifa()
{
    memset(ui_vj, 0, sizeof(ui_vj));
    memset(stB, true, sizeof stB); // vj, 列位势
    memset(stA, true, sizeof stA); // ui, 行位势
    // 初始时刻，所有位势都是可覆写的
    // 当被计算一次之后便不可再计算

    ui_vj[0][SailPlace] = 0; // 假设u1 == 0
    stA[0] = false;

    // 从前往后 遍历不一定能够保证所所有位势均可一次性遍历完整，需要二次遍历
    // 从后往前 一定能保证 一次遍历就能够求出所有位势
    for (int i = 0; i < CreatePlace; i++)
    {
        for (int j = SailPlace - 1; j >= 0; j--)
        {
            if (back03[i][j] != 0) // 基变量（非零格）求解位势
            {
                if (stA[i] == true) // ui
                {
                    stA[i] = false;
                    ui_vj[i][SailPlace] = priceij[i][j] - ui_vj[CreatePlace][j]; // ui = cij - vj
                }
                else if (stB[j] == true)
                {
                    stB[j] = false;
                    ui_vj[CreatePlace][j] = priceij[i][j] - ui_vj[i][SailPlace];
                }
                else
                {
                    cout << "错误！" << endl;
                }
            }
        }
    }
}

void Space_weishi()
{
    for (int i = 0; i < CreatePlace; i++)
    {
        for (int j = 0; j < SailPlace; j++)
        {
            if (back03[i][j] == 0) // 可行解的空格处
            {
                ui_vj[i][j] = ui_vj[CreatePlace][j] + ui_vj[i][SailPlace];
            }
        }
    }
}

void CheckSpace() // 空格的检验数表
{
    // 如果某个检验格子的值 小于 0， 证明还可以再优化
    // 如果某个检验格子的值 等于 0， 证明有多重解
    // 如果某个检验格子的值 大于 0， 证明这个位置已经时最优解了，任何变化都将引起总运输费用的上升
    // 后续步骤多一步处理

    memset(space_check, 0, sizeof(space_check));

    for (int i = 0; i < CreatePlace; i++)
    {
        for (int j = 0; j < SailPlace; j++)
        {
            if (ui_vj[i][j] != 0)
            {
                space_check[i][j] = priceij[i][j] - ui_vj[i][j];
            }
            else
            {
                // 排除非空格（基变量）的影响
                space_check[i][j] = 0x3f3f3f;
            }
        }
    }
}

void loop_find(int, int);

// 回路法求解调整路径
void loop_best() // 回路法求解最优路径
{
    for (int i = 0; i < CreatePlace; i++)
    {
        for (int j = 0; j < SailPlace; j++) // 遍历空格检验表寻找小于0的检验数，然后优化对应的回路
        {
            if (space_check[i][j] < 0) // 找到目标检验数
            {
                loop_find(i, j); // 开始寻找回路并优化
            }
        }
    }
}

void loop_find(int x, int y)
{
    int cnt = 1; // 记录真实的顶点个数
    int pt;      // 循环控制变量，记录对应的方向，帮助下一步的方向判断

    int xx, yy;

    Point pmin;
    pmin.num = 1e8;

    loop Loop; // 只需要找到一个回路
    Loop.path.push_back({x, y, back03[x][y], 1});

    for (int i = 0; i < 4; i++) // 每一种最初的方向都看一遍
    {
        cnt = 1;
        pt = i; // 记录出发的方向
        xx = x + x03[i];
        yy = y + y03[i];

        // 一个空格有且仅有一个回路
        if (xx == x && yy == y) // 一个空格找到一个回路就可以了
        {
            break;
        }

        while (xx >= 0 && xx < CreatePlace && yy >= 0 && yy <= SailPlace) // 不出界并且没找到回路
        {
            if (back03[xx][yy] == 0) // 没有碰到数字顶点
            {
                xx = xx + x03[pt]; // 沿着pt的方向一直走下去
                yy = yy + y03[pt];

                if (xx == x && yy == y)
                    break;
            }
            else
            {
                cnt++;             // 找到了回路的一个顶点
                pt = (pt + 1) % 4; // 换个方向

                Point p;
                p.ii = xx;
                p.jj = yy;
                p.num = back03[xx][yy];
                p.xuhao = cnt;

                Loop.path.push_back(p);

                if (cnt % 2 == 0 && pmin.num > p.num) // 偶数顶点 && 找到更小的
                {
                    pmin = p;
                }

                xx = xx + x03[pt];
                yy = yy + y03[pt];

                if (xx == x && yy == y)
                    break;
            }
        }

        if (xx < 0 || xx >= CreatePlace || yy < 0 || yy >= SailPlace) // 出界 是因为出界而不是因为没有找到回路
        {
            while (cnt != 1)
            {
                Loop.path.pop_back(); // 弹出无效数据
                cnt--;
            }
        }
    }

    while (Loop.path.empty() == false)
    {
        auto vtmp = Loop.path.back();
        Loop.path.pop_back();

        if (vtmp.xuhao % 2 != 0) // 奇数位
        {
            vtmp.num += pmin.num;
            back03[vtmp.ii][vtmp.jj] = vtmp.num;
        }
        else // 偶数位
        {
            vtmp.num -= pmin.num;
            back03[vtmp.ii][vtmp.jj] = vtmp.num;
        }
    }
}

int main()
{
    cout << "第 三 题 ----------------------------------------------------------" << endl;
    cout << "\n";

    for (int i = 0; i < CreatePlace; i++)
    {
        for (int j = 0; j < SailPlace; j++)
        {
            price tmp;
            tmp.i = i;
            tmp.j = j;
            tmp.cij = priceij[i][j];

            qu03.push(tmp);
        }
    }

    findmin(); // 使用最小元素法求出一种可行解

    Weishifa(); // 求解行位势和列位势

    Space_weishi(); // 求解空格（非基变量）的（ui+vj)

    CheckSpace(); // 空格的检验数表

    loop_best(); // 回路法求解最优路径

    print();

    return 0;
}
